'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-10-13 16:14:41
LastEditTime: 2025-10-13 16:33:10
'''



class Solution:

    def orangesRotting(self, grid):

        M = len(grid)
        N = len(grid[0])
        # 寻找腐烂的橘子的位置
        queue = []
        # 统计新鲜橘子的个数
        count = 0

        for r in range(M):
            for c in range(N):
                if grid[r][c] == 1:
                    count += 1


                elif grid[r][c] == 2:
                    queue.append((r, c))
        
        round = 0

        while count and queue:
            round += 1
            
            n = len(queue)
            for _ in range(n):
                r, c = queue.pop(0)
                if r - 1 >= 0 and grid[r - 1][c] == 1:
                    grid[r - 1][c] = 2
                    count -= 1
                    queue.append((r - 1, c))
                
                if r + 1 < M and grid[r + 1][c] == 1:
                    grid[r + 1][c] = 2
                    count -= 1
                    queue.append((r + 1, c))

                if c - 1 >= 0 and grid[r][c - 1] == 1:
                    grid[r][c - 1] = 2
                    count -= 1
                    queue.append((r, c - 1))

                if c + 1 < N and grid[r][c + 1] == 1:

                    grid[r][c + 1] = 2
                    count -= 1
                    queue.append((r, c + 1))
        if count > 0:
            return -1

        return round   
                

